<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">
 <meta>
  <!-- Stylesheets -->
  <link href="../web.css" type="text/css" rel="stylesheet"></link>
  <link href="../pygmentize.css" type="text/css" rel="stylesheet"></link>
  <title>VLFeat - Documentation - C API</title>
  <link rel="stylesheet" type="text/css" href="../doxygen.css"></style>

  <!-- Scripts-->
  
 </meta>

 <!-- Body Start -->
 <body>
  <div id="header">
   <!-- Google CSE Search Box Begins -->
   <form action="http://www.vlfeat.org/search.html" method="get" id="cse-search-box" enctype="application/x-www-form-urlencoded">
    <div>
     <input type="hidden" name="cx" value="003215582122030917471:oq23albfeam"></input>
     <input type="hidden" name="cof" value="FORID:11"></input>
     <input type="hidden" name="ie" value="UTF-8"></input>
     <input type="text" name="q" size="31"></input>
     <input type="submit" name="sa" value="Search"></input>
    </div>
   </form>
   <script src="http://www.google.com/coop/cse/brand?form=cse-search-box&amp;lang=en" xml:space="preserve" type="text/javascript"></script>
   <!-- Google CSE Search Box Ends -->
   <h1><a shape="rect" href="../index.html" class="plain"><span id="vlfeat">VLFeat</span><span id="dotorg">.org</span></a></h1>
  </div>
  <div id="headbanner">
   Documentation - C API
  </div>
  <div id="pagebody">
   <div id="sidebar"> <!-- Navigation Start -->
    <ul>
<li><a href="../index.html">Home</a>
</li>
<li><a href="../download.html">Download</a>
</li>
<li><a href="../doc.html">Documentation</a>
<ul>
<li><a href="../mdoc/mdoc.html">Matlab API</a>
</li>
<li><a href="index.html" class='active' >C API</a>
</li>
<li><a href="../man/man.html">Man pages</a>
</li>
</ul></li>
<li><a href="../overview/tut.html">Tutorials</a>
</li>
<li><a href="../applications/apps.html">Applications</a>
</li>
</ul>

   </div> <!-- sidebar -->
   <div id="content">
    
    <link rel="stylesheet" type="text/css" href="../doxygen.css"></style>
    <div class="doxygen">
<div>
<!-- Generated by Doxygen 1.7.5.1 -->
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li><a href="pages.html"><span>Related&#160;Pages</span></a></li>
      <li><a href="annotated.html"><span>Data&#160;Structures</span></a></li>
      <li class="current"><a href="files.html"><span>Files</span></a></li>
    </ul>
  </div>
  <div id="navrow2" class="tabs2">
    <ul class="tablist">
      <li><a href="files.html"><span>File&#160;List</span></a></li>
      <li><a href="globals.html"><span>Globals</span></a></li>
    </ul>
  </div>
</div>
<div class="header">
  <div class="summary">
<a href="#define-members">Defines</a> &#124;
<a href="#func-members">Functions</a>  </div>
  <div class="headertitle">
<div class="title">heap-def.h File Reference</div>  </div>
</div>
<div class="contents">

<p>Heap preprocessor metaprogram.  
<a href="#details">More...</a></p>
<div class="textblock"><code>#include &quot;<a class="el" href="host_8h.html">host.h</a>&quot;</code><br/>
<code>#include &lt;assert.h&gt;</code><br/>
</div><table class="memberdecls">
<tr><td colspan="2"><h2><a name="define-members"></a>
Defines</h2></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">#define&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="heap-def_8h.html#ac2b59b9373be3df851dac7c594924a92">VL_HEAP_array</a>&#160;&#160;&#160;VL_HEAP_type*</td></tr>
<tr><td class="memItemLeft" align="right" valign="top">#define&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="heap-def_8h.html#ae0d8f7e617493c4a73696983e1c360b6">VL_HEAP_prefix</a>&#160;&#160;&#160;HeapObject</td></tr>
<tr><td class="memItemLeft" align="right" valign="top">#define&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="heap-def_8h.html#a809b241c547ba76275bd10575086c3b2">VL_HEAP_type</a>&#160;&#160;&#160;HeapType</td></tr>
<tr><td class="memItemLeft" align="right" valign="top">#define&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="heap-def_8h.html#ac2b59b9373be3df851dac7c594924a92">VL_HEAP_array</a>&#160;&#160;&#160;HeapType*</td></tr>
<tr><td class="memItemLeft" align="right" valign="top">#define&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="heap-def_8h.html#ac2b59b9373be3df851dac7c594924a92">VL_HEAP_array</a>&#160;&#160;&#160;HeapType const*</td></tr>
<tr><td colspan="2"><h2><a name="func-members"></a>
Functions</h2></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="heap-def_8h.html#a7256f361601ba43113c862d9477f1d4b">vl_heap_parent</a> (<a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a> index)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Get index of parent node.  <a href="#a7256f361601ba43113c862d9477f1d4b"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="heap-def_8h.html#a95b7f92afacd889da252d5a77fde5d05">vl_heap_left_child</a> (<a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a> index)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Get index of left child.  <a href="#a95b7f92afacd889da252d5a77fde5d05"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="heap-def_8h.html#aacfa305e511251faa8cfb8b7114a31f7">vl_heap_right_child</a> (<a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a> index)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Get index of right child.  <a href="#aacfa305e511251faa8cfb8b7114a31f7"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">VL_HEAP_type&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="heap-def_8h.html#af926f2b2ea17e5adcf6ab144d87f96e2">VL_HEAP_cmp</a> (VL_HEAP_array_const array, <a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a> indexA, <a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a> indexB)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Compare two heap elements.  <a href="#af926f2b2ea17e5adcf6ab144d87f96e2"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="heap-def_8h.html#a23f32c850484c8824785a17e9d93272b">VL_HEAP_swap</a> (VL_HEAP_array array, <a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a> indexA, <a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a> indexB)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Swap two heap elements.  <a href="#a23f32c850484c8824785a17e9d93272b"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="heap-def_8h.html#a8c4d40e0b2309f0d897a8b1e9a55d726">VL_HEAP_up</a> (VL_HEAP_array array, <a class="el" href="host_8h.html#a0ee26101458c663510d620e3ee7e2555">vl_size</a> heapSize, <a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a> index)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Heap up operation.  <a href="#a8c4d40e0b2309f0d897a8b1e9a55d726"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="heap-def_8h.html#affd0336086a1762e0ac2cace28c9656a">VL_HEAP_down</a> (VL_HEAP_array array, <a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a> index)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Heap down operation.  <a href="#affd0336086a1762e0ac2cace28c9656a"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="heap-def_8h.html#ab8d30a74d7d51d3ed4c9f3e35ef6c638">VL_HEAP_push</a> (VL_HEAP_array array, <a class="el" href="host_8h.html#a0ee26101458c663510d620e3ee7e2555">vl_size</a> *heapSize)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Heap push operation.  <a href="#ab8d30a74d7d51d3ed4c9f3e35ef6c638"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="heap-def_8h.html#ac9e07a24d045fbc08853213bc84be5ea">VL_HEAP_pop</a> (VL_HEAP_array array, <a class="el" href="host_8h.html#a0ee26101458c663510d620e3ee7e2555">vl_size</a> *heapSize)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Heap pop operation.  <a href="#ac9e07a24d045fbc08853213bc84be5ea"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="heap-def_8h.html#a6718e132e6bfabc177ca2f5115dd6452">VL_HEAP_update</a> (VL_HEAP_array array, <a class="el" href="host_8h.html#a0ee26101458c663510d620e3ee7e2555">vl_size</a> heapSize, <a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a> index)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Heap update operation.  <a href="#a6718e132e6bfabc177ca2f5115dd6452"></a><br/></td></tr>
</table>
<hr/><a name="details" id="details"></a><h2>Detailed Description</h2>
<div class="textblock"><dl class="author"><dt><b>Author:</b></dt><dd>Andrea Vedaldi</dd></dl>
<p>A heap organizes an array of objects in a priority queue. This module is a template metaprogram that defines heap operations on array of generic objects, or even generic object containers.</p>
<ul>
<li><a class="el" href="heap-def_8h.html#heap-def-overview">Overview</a><ul>
<li><a class="el" href="heap-def_8h.html#heap-def-overview-general">General usage</a></li>
</ul>
</li>
<li><a class="el" href="heap-def_8h.html#heap-def-tech">Technical details</a></li>
</ul>
<h2><a class="anchor" id="heap-def-overview"></a>
Overview</h2>
<p>To use <a class="el" href="heap-def_8h.html">heap-def.h</a> one must specify at least a prefix and the data type for the heap elements:</p>
<div class="fragment"><pre class="fragment"><span class="preprocessor"> #define VL_HEAP_prefix  my_heap</span>
<span class="preprocessor"></span><span class="preprocessor"> #define VL_HEAP_type    float</span>
<span class="preprocessor"> #include &lt;vl/heap-def.h&gt;</span>
</pre></div><p>This code fragment defines a number of functions prefixed by <a class="el" href="heap-def_8h.html#ae0d8f7e617493c4a73696983e1c360b6">VL_HEAP_prefix</a>, such as <code>my_heap_push</code> (<a class="el" href="heap-def_8h.html#ab8d30a74d7d51d3ed4c9f3e35ef6c638" title="Heap push operation.">VL_HEAP_push</a>) and <code>my_heap_pop</code> (<a class="el" href="heap-def_8h.html#ac9e07a24d045fbc08853213bc84be5ea" title="Heap pop operation.">VL_HEAP_pop</a>), that implement the heap operations. These functions operate on an array that has type <a class="el" href="heap-def_8h.html#ac2b59b9373be3df851dac7c594924a92">VL_HEAP_array</a>. By default, this is defined to be:</p>
<div class="fragment"><pre class="fragment"><span class="preprocessor"> #define VL_HEAP_array VL_HEAP_type*</span>
<span class="preprocessor"> #define VL_HEAP_array_const VL_HEAP_type const*</span>
</pre></div><p>The array itself is accessed uniquely by means of two functions:</p>
<ul>
<li><a class="el" href="heap-def_8h.html#af926f2b2ea17e5adcf6ab144d87f96e2" title="Compare two heap elements.">VL_HEAP_cmp</a>, that compares two array elements. The default implementation assumes that <a class="el" href="heap-def_8h.html#a809b241c547ba76275bd10575086c3b2">VL_HEAP_type</a> is numeric.</li>
<li><a class="el" href="heap-def_8h.html#a23f32c850484c8824785a17e9d93272b" title="Swap two heap elements.">VL_HEAP_swap</a>, that swaps two array elements. The default implementation assumes that <a class="el" href="heap-def_8h.html#a809b241c547ba76275bd10575086c3b2">VL_HEAP_type</a> can be copied by the <code>=</code> operator.</li>
</ul>
<p>The heap state is a integer <code>numElements</code> (of type <a class="el" href="host_8h.html#a0ee26101458c663510d620e3ee7e2555" title="Unsigned integer holding the size of a memory block.">vl_size</a>) counting the number of elements of the array that are currently part of the heap and the content of the first <code>numElements</code> elements of the array. The portion of the array that constitutes the heap satisfies a certain invariant property (heap property, <a class="el" href="heap-def_8h.html#heap-def-tech">Technical details</a>). From a user viewpoint, the most important consequence is that the first element of the array (the one of index 0) is also the smallest (according to <a class="el" href="heap-def_8h.html#af926f2b2ea17e5adcf6ab144d87f96e2" title="Compare two heap elements.">VL_HEAP_cmp</a>).</p>
<p>Elements are added to the heap by <a class="el" href="heap-def_8h.html#ab8d30a74d7d51d3ed4c9f3e35ef6c638" title="Heap push operation.">VL_HEAP_push</a> and removed from the heap by <a class="el" href="heap-def_8h.html#ac9e07a24d045fbc08853213bc84be5ea" title="Heap pop operation.">VL_HEAP_pop</a>. A push operation adds to the heap the array element immediately after the last element already in the heap (i.e. the element of index <code>numElements</code>) and increases the number of heap elements <code>numElements</code>. Elements in the heap are swapped as required in order to maintain the heap consistency. Similarly, a pop operation removes the first (smaller) element from the heap and decreases the number of heap elements <code>numElements</code>.</p>
<p>The values of nodes currently in the heap can be updated by <a class="el" href="heap-def_8h.html#a6718e132e6bfabc177ca2f5115dd6452" title="Heap update operation.">VL_HEAP_update</a>. Notice however that using this function requires knowing the index of the element that needs to be updated up to the swapping operations that the heap performs to maintain consistency. Typically, this requires redefining <a class="el" href="heap-def_8h.html#a23f32c850484c8824785a17e9d93272b" title="Swap two heap elements.">VL_HEAP_swap</a> to keep track of such changes (<a class="el" href="heap-def_8h.html#heap-def-overview-general">General usage</a>).</p>
<h3><a class="anchor" id="heap-def-overview-general"></a>
General usage</h3>
<p>The heap container may be mapped to any type by reimplementing <a class="el" href="heap-def_8h.html#af926f2b2ea17e5adcf6ab144d87f96e2" title="Compare two heap elements.">VL_HEAP_cmp</a> and <a class="el" href="heap-def_8h.html#a23f32c850484c8824785a17e9d93272b" title="Swap two heap elements.">VL_HEAP_swap</a> explicitly. For instance the following code redefines <a class="el" href="heap-def_8h.html#af926f2b2ea17e5adcf6ab144d87f96e2" title="Compare two heap elements.">VL_HEAP_cmp</a> to deal with the case in which the heap is an array of structures:</p>
<div class="fragment"><pre class="fragment"> <span class="keyword">typedef</span> <span class="keyword">struct </span>_S { <span class="keywordtype">int</span> x ; } S ;
 <span class="keywordtype">int</span> s_cmp (S <span class="keyword">const</span> * v, <a class="code" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc" title="Same as vl_size.">vl_uindex</a> a, <a class="code" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc" title="Same as vl_size.">vl_uindex</a> b) {
   <span class="keywordflow">return</span> v[a].x - v[b].x ;
 }
<span class="preprocessor"> #define VL_HEAP_prefix  s_heap</span>
<span class="preprocessor"></span><span class="preprocessor"> #define VL_HEAP_type    S</span>
<span class="preprocessor"></span><span class="preprocessor"> #define VL_HEAP_cmp     s_cmp</span>
<span class="preprocessor"> #include &lt;vl/heap-def.h&gt;</span>
</pre></div><p>In the following example, the heap itself is an arbitrary structure:</p>
<div class="fragment"><pre class="fragment"> <span class="keyword">typedef</span> <span class="keyword">struct </span>_H { <span class="keywordtype">int</span>* array ; } H ;
 <span class="keywordtype">int</span> h_cmp (H <span class="keyword">const</span> * h, <a class="code" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc" title="Same as vl_size.">vl_uindex</a> a, <a class="code" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc" title="Same as vl_size.">vl_uindex</a> b) {
   <span class="keywordflow">return</span> h-&gt;array[a] - h-&gt;array[b] ;
 }
 <span class="keywordtype">int</span> h_swap (H * h, <a class="code" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc" title="Same as vl_size.">vl_uindex</a> a, <a class="code" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc" title="Same as vl_size.">vl_uindex</a> b) {
   <span class="keywordtype">int</span> t = h-&gt;array[a] ;
   h-&gt;array[a] = h-&gt;array[b] ;
   h-&gt;array[b] = t ;
 }
<span class="preprocessor"> #define VL_HEAP_prefix  h_heap</span>
<span class="preprocessor"></span><span class="preprocessor"> #define VL_HEAP_swap    h_swap</span>
<span class="preprocessor"></span><span class="preprocessor"> #define VL_HEAP_cmp     h_cmp</span>
<span class="preprocessor"> #include &lt;vl/heap-def.h&gt;</span>
</pre></div><h2><a class="anchor" id="heap-def-tech"></a>
Technical details</h2>
<p>The heap is organised as a binary tree with the property (<em>heap property</em>) that any node is not larger than any of its children. In particular, the root is the smallest node.</p>
<p><a class="el" href="heap-def_8h.html">heap-def.h</a> uses the standard binary tree representation as a linear array. Tree nodes are mapped to array elements as follows: <code>array[0]</code> corresponds to the root, <code>array[1]</code> and <code>array[2]</code> to the root left and right children and so on. In this way, the tree structure is fully specified by the total number of nodes <code>N</code>.</p>
<p>Assuming that the heap has <code>N</code> nodes (from <code>array[0]</code> to <code>array[N-1]</code>), adding the node <code>array[N]</code> to the heap is done by a <em>push down</em> operation: if the node <code>array[N]</code> is smaller than its parent (violating the heap property) it is pushed down by swapping it with the parent, and so on recursively.</p>
<p>Removing the smallest element <code>array[0]</code> with an heap of <code>N</code> nodes is done by swapping <code>array[0]</code> with <code>array[N-1]</code>. If then <code>array[0]</code> is larger than any of its children, it is swapped with the smallest of the two and so on recursively (<em>push up</em> operation).</p>
<p>Restoring the heap property after an element <code>array[i]</code> has been modified can be done by a push up or push down operation on that node. </p>
</div><hr/><h2>Define Documentation</h2>
<a class="anchor" id="ac2b59b9373be3df851dac7c594924a92"></a><!-- doxytag: member="heap&#45;def.h::VL_HEAP_array" ref="ac2b59b9373be3df851dac7c594924a92" args="" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">#define VL_HEAP_array&#160;&#160;&#160;VL_HEAP_type*</td>
        </tr>
      </table>
</div>
<div class="memdoc">
<p>Data type of the heap container</p>
<p>Const data type of the heap container </p>

</div>
</div>
<a class="anchor" id="ac2b59b9373be3df851dac7c594924a92"></a><!-- doxytag: member="heap&#45;def.h::VL_HEAP_array" ref="ac2b59b9373be3df851dac7c594924a92" args="" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">#define VL_HEAP_array&#160;&#160;&#160;HeapType*</td>
        </tr>
      </table>
</div>
<div class="memdoc">
<p>Data type of the heap container</p>
<p>Const data type of the heap container </p>

</div>
</div>
<a class="anchor" id="ac2b59b9373be3df851dac7c594924a92"></a><!-- doxytag: member="heap&#45;def.h::VL_HEAP_array" ref="ac2b59b9373be3df851dac7c594924a92" args="" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">#define VL_HEAP_array&#160;&#160;&#160;HeapType const*</td>
        </tr>
      </table>
</div>
<div class="memdoc">
<p>Data type of the heap container</p>
<p>Const data type of the heap container </p>

</div>
</div>
<a class="anchor" id="ae0d8f7e617493c4a73696983e1c360b6"></a><!-- doxytag: member="heap&#45;def.h::VL_HEAP_prefix" ref="ae0d8f7e617493c4a73696983e1c360b6" args="" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">#define VL_HEAP_prefix&#160;&#160;&#160;HeapObject</td>
        </tr>
      </table>
</div>
<div class="memdoc">
<p>Prefix of the heap functions </p>

</div>
</div>
<a class="anchor" id="a809b241c547ba76275bd10575086c3b2"></a><!-- doxytag: member="heap&#45;def.h::VL_HEAP_type" ref="a809b241c547ba76275bd10575086c3b2" args="" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">#define VL_HEAP_type&#160;&#160;&#160;HeapType</td>
        </tr>
      </table>
</div>
<div class="memdoc">
<p>Data type of the heap elements </p>

</div>
</div>
<hr/><h2>Function Documentation</h2>
<a class="anchor" id="af926f2b2ea17e5adcf6ab144d87f96e2"></a><!-- doxytag: member="heap&#45;def.h::VL_HEAP_cmp" ref="af926f2b2ea17e5adcf6ab144d87f96e2" args="(VL_HEAP_array_const array, vl_uindex indexA, vl_uindex indexB)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">VL_HEAP_type VL_HEAP_cmp </td>
          <td>(</td>
          <td class="paramtype">VL_HEAP_array_const&#160;</td>
          <td class="paramname"><em>array</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a>&#160;</td>
          <td class="paramname"><em>indexA</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a>&#160;</td>
          <td class="paramname"><em>indexB</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">
<dl><dt><b>Parameters:</b></dt><dd>
  <table class="params">
    <tr><td class="paramname">array</td><td>heap array. </td></tr>
    <tr><td class="paramname">indexA</td><td>index of the first element <code>A</code> to compare. </td></tr>
    <tr><td class="paramname">indexB</td><td>index of the second element <code>B</code> to comapre. </td></tr>
  </table>
  </dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd>a negative number if <code>A&lt;B</code>, 0 if <code>A==B</code>, and a positive number if if <code>A&gt;B</code>. </dd></dl>

</div>
</div>
<a class="anchor" id="affd0336086a1762e0ac2cace28c9656a"></a><!-- doxytag: member="heap&#45;def.h::VL_HEAP_down" ref="affd0336086a1762e0ac2cace28c9656a" args="(VL_HEAP_array array, vl_uindex index)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">void VL_HEAP_down </td>
          <td>(</td>
          <td class="paramtype">VL_HEAP_array&#160;</td>
          <td class="paramname"><em>array</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a>&#160;</td>
          <td class="paramname"><em>index</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">
<dl><dt><b>Parameters:</b></dt><dd>
  <table class="params">
    <tr><td class="paramname">array</td><td>pointer to the heap node array. </td></tr>
    <tr><td class="paramname">index</td><td>index of the node to push up. </td></tr>
  </table>
  </dd>
</dl>

</div>
</div>
<a class="anchor" id="a95b7f92afacd889da252d5a77fde5d05"></a><!-- doxytag: member="heap&#45;def.h::vl_heap_left_child" ref="a95b7f92afacd889da252d5a77fde5d05" args="(vl_uindex index)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a> vl_heap_left_child </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a>&#160;</td>
          <td class="paramname"><em>index</em></td><td>)</td>
          <td><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">
<dl><dt><b>Parameters:</b></dt><dd>
  <table class="params">
    <tr><td class="paramname">index</td><td>a node index. </td></tr>
  </table>
  </dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd>index of the left child. </dd></dl>

</div>
</div>
<a class="anchor" id="a7256f361601ba43113c862d9477f1d4b"></a><!-- doxytag: member="heap&#45;def.h::vl_heap_parent" ref="a7256f361601ba43113c862d9477f1d4b" args="(vl_uindex index)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a> vl_heap_parent </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a>&#160;</td>
          <td class="paramname"><em>index</em></td><td>)</td>
          <td><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">
<dl><dt><b>Parameters:</b></dt><dd>
  <table class="params">
    <tr><td class="paramname">index</td><td>a node index. </td></tr>
  </table>
  </dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd>index of the parent node. </dd></dl>

</div>
</div>
<a class="anchor" id="ac9e07a24d045fbc08853213bc84be5ea"></a><!-- doxytag: member="heap&#45;def.h::VL_HEAP_pop" ref="ac9e07a24d045fbc08853213bc84be5ea" args="(VL_HEAP_array array, vl_size *heapSize)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a> VL_HEAP_pop </td>
          <td>(</td>
          <td class="paramtype">VL_HEAP_array&#160;</td>
          <td class="paramname"><em>array</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="host_8h.html#a0ee26101458c663510d620e3ee7e2555">vl_size</a> *&#160;</td>
          <td class="paramname"><em>heapSize</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">
<dl><dt><b>Parameters:</b></dt><dd>
  <table class="params">
    <tr><td class="paramname">array</td><td>pointer to the heap array. </td></tr>
    <tr><td class="paramname">heapSize</td><td>(in/out) size of the heap. </td></tr>
  </table>
  </dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd>index of the popped element.</dd></dl>
<p>The function extracts from the heap the element of index 0 (the smallest element) and decreases <code>heapSize</code>.</p>
<p>The element extracted is moved as the first element after the heap end (thus it has index <code>heapSize</code>). For convenience, this index is returned by the function.</p>
<p>Popping from an empty heap is undefined. </p>

</div>
</div>
<a class="anchor" id="ab8d30a74d7d51d3ed4c9f3e35ef6c638"></a><!-- doxytag: member="heap&#45;def.h::VL_HEAP_push" ref="ab8d30a74d7d51d3ed4c9f3e35ef6c638" args="(VL_HEAP_array array, vl_size *heapSize)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">void VL_HEAP_push </td>
          <td>(</td>
          <td class="paramtype">VL_HEAP_array&#160;</td>
          <td class="paramname"><em>array</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="host_8h.html#a0ee26101458c663510d620e3ee7e2555">vl_size</a> *&#160;</td>
          <td class="paramname"><em>heapSize</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">
<dl><dt><b>Parameters:</b></dt><dd>
  <table class="params">
    <tr><td class="paramname">array</td><td>pointer to the heap array. </td></tr>
    <tr><td class="paramname">heapSize</td><td>(in/out) size of the heap.</td></tr>
  </table>
  </dd>
</dl>
<p>The function adds to the heap the element of index <code>heapSize</code> and increments <code>heapSize</code>. </p>

</div>
</div>
<a class="anchor" id="aacfa305e511251faa8cfb8b7114a31f7"></a><!-- doxytag: member="heap&#45;def.h::vl_heap_right_child" ref="aacfa305e511251faa8cfb8b7114a31f7" args="(vl_uindex index)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a> vl_heap_right_child </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a>&#160;</td>
          <td class="paramname"><em>index</em></td><td>)</td>
          <td><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">
<dl><dt><b>Parameters:</b></dt><dd>
  <table class="params">
    <tr><td class="paramname">index</td><td>a node index. </td></tr>
  </table>
  </dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd>index of the right child. </dd></dl>

</div>
</div>
<a class="anchor" id="a23f32c850484c8824785a17e9d93272b"></a><!-- doxytag: member="heap&#45;def.h::VL_HEAP_swap" ref="a23f32c850484c8824785a17e9d93272b" args="(VL_HEAP_array array, vl_uindex indexA, vl_uindex indexB)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">void VL_HEAP_swap </td>
          <td>(</td>
          <td class="paramtype">VL_HEAP_array&#160;</td>
          <td class="paramname"><em>array</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a>&#160;</td>
          <td class="paramname"><em>indexA</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a>&#160;</td>
          <td class="paramname"><em>indexB</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">
<dl><dt><b>Parameters:</b></dt><dd>
  <table class="params">
    <tr><td class="paramname">array</td><td>array of nodes. </td></tr>
    <tr><td class="paramname">array</td><td>heap array. </td></tr>
    <tr><td class="paramname">indexA</td><td>index of the first node to swap. </td></tr>
    <tr><td class="paramname">indexB</td><td>index of the second node to swap.</td></tr>
  </table>
  </dd>
</dl>
<p>The function swaps the two heap elements <em>a</em> and @ b. The function uses a temporary element and the copy operator, which must be well defined for the heap elements. </p>

</div>
</div>
<a class="anchor" id="a8c4d40e0b2309f0d897a8b1e9a55d726"></a><!-- doxytag: member="heap&#45;def.h::VL_HEAP_up" ref="a8c4d40e0b2309f0d897a8b1e9a55d726" args="(VL_HEAP_array array, vl_size heapSize, vl_uindex index)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">void VL_HEAP_up </td>
          <td>(</td>
          <td class="paramtype">VL_HEAP_array&#160;</td>
          <td class="paramname"><em>array</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="host_8h.html#a0ee26101458c663510d620e3ee7e2555">vl_size</a>&#160;</td>
          <td class="paramname"><em>heapSize</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a>&#160;</td>
          <td class="paramname"><em>index</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">
<dl><dt><b>Parameters:</b></dt><dd>
  <table class="params">
    <tr><td class="paramname">array</td><td>pointer to the heap array. </td></tr>
    <tr><td class="paramname">heapSize</td><td>size of the heap. </td></tr>
    <tr><td class="paramname">index</td><td>index of the node to push up. </td></tr>
  </table>
  </dd>
</dl>

</div>
</div>
<a class="anchor" id="a6718e132e6bfabc177ca2f5115dd6452"></a><!-- doxytag: member="heap&#45;def.h::VL_HEAP_update" ref="a6718e132e6bfabc177ca2f5115dd6452" args="(VL_HEAP_array array, vl_size heapSize, vl_uindex index)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">void VL_HEAP_update </td>
          <td>(</td>
          <td class="paramtype">VL_HEAP_array&#160;</td>
          <td class="paramname"><em>array</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="host_8h.html#a0ee26101458c663510d620e3ee7e2555">vl_size</a>&#160;</td>
          <td class="paramname"><em>heapSize</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="host_8h.html#ac13bd3cc913e1da576e189a3ec8d66fc">vl_uindex</a>&#160;</td>
          <td class="paramname"><em>index</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">
<dl><dt><b>Parameters:</b></dt><dd>
  <table class="params">
    <tr><td class="paramname">array</td><td>pointer to the heap array. </td></tr>
    <tr><td class="paramname">heapSize</td><td>size of the heap. </td></tr>
    <tr><td class="paramname">index</td><td>index of the node to update.</td></tr>
  </table>
  </dd>
</dl>
<p>The function updates the heap to account for a change to the element of index <code>index</code> in the heap.</p>
<p>Notice that using this function requires knowing the index of the heap index of element that was changed. Since the heap swaps elements in the array, this is in general different from the index that that element had originally. </p>

</div>
</div>
</div>
     <!-- Doc Here -->
    </div>
   
   </div>
   <div class="clear">&nbsp;</div>
  </div> <!-- pagebody -->
  <div id="footer">
   &copy; 2007-12 Andrea Vedaldi and Brian Fulkerson
  </div> <!-- footer -->

  <!-- Google Analytics Begins -->
  <script xml:space="preserve" type="text/javascript">
   //<![CDATA[
    var localre = /vlfeat.org/;
    if(document.location.host.search(localre) != -1)
    {
   var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
   document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
   }
   //]]>
  </script>
  <script xml:space="preserve" type="text/javascript">
    //<![CDATA[
    var localre = /vlfeat.org/;
    if(document.location.host.search(localre) != -1)
    {

   try {
   var pageTracker = _gat._getTracker("UA-4936091-2");
   pageTracker._trackPageview();
   } catch(err) {}

   }
   //]]>
  </script>
  <!-- Google Analytics Ends -->
 </body>
</html>

 
